package sort;

import java.util.Arrays;

/**
 * 描述:
 *
 * @author
 * @created 2021/12/30 18:48
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 6, 67, 7, 87, 4, 3, 23, 45, 6, 7, 78, 6, 4, 43, 5, 6, 67, 67};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {
        /*先将数组转换为堆结构*/

        /*实现一个循环，表示一个元素有序，每次都把堆排序最大的下标向前移一个*/
        for (int end = arr.length - 1; end > 0; end--) {
            /*将堆结构不断调整为大根堆*/
            maxHeap(arr, end);
            /*将堆顶的元素和堆得最后一个叶子节点进行交换，表示这个元素有序*/
            int temp = arr[0];
            arr[0] = arr[end];
            arr[end] = temp;
        }

    }

    public static void maxHeap(int[] arr, int end) {
        /*先求出最后一个父节点的位置，然后每向前推一格，都是父节点*/
        int lastFather = end % 2 == 0 ? end / 2 - 1 : end / 2;
        /*从最后一个父节点开始向前不断减1，使得每个父节点都能根孩子pk*/
        for (int father = lastFather; father >= 0; father--) {
            /*根据父节点的下标推算出左右孩子的下标*/
            /*左孩子 2n + 1*/
            /*右孩子 2n + 2*/
            int left = father * 2 + 1;
            int right = father * 2 + 2;
            /*在保证右孩子下标没有越界的情况下，使用右孩子和父节点进行比较*/
            /*如果右孩子大于父节点，则交换*/
            if (right <= end && arr[right] > arr[father]) {
                int temp = arr[right];
                arr[right] = arr[father];
                arr[father] = temp;
            }
            /*使用左孩子和父节点比较，如果左孩子大于父节点，则交换*/
            if (arr[left] > arr[father]) {
                int temp = arr[left];
                arr[left] = arr[father];
                arr[father] = temp;
            }
        }
    }

}
